//
// Created by Lenovo on 2024/3/7.
//
#include<bits/stdc++.h>
using namespace std;
//单词接龙
class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        //将wordList转为wordSet，便于查询
        set<string> wordSet(wordList.begin(),wordList.end());
        //没有endWord的情况
        if(wordSet.find(endWord)==wordSet.end()) return 0;
        //key--对应的单词，value--转换到该单词所需的路径长度（可标记该单词是否访问过）
        map<string,int> pathMap;
        pathMap[beginWord]=1;
        //求转换需要的最短路径，采用bfs搜索最方便
        queue<string> que;
        que.push(beginWord);
        while(!que.empty()){
            string word=que.front();
            que.pop();
            int path=pathMap[word];
            //遍历word的每个字母，替换成别的字母得到新单词
            for(int i=0;i<word.size();i++){
                string newWord=word;
                for(int j=0;j<26;j++){
                    newWord[i]=j+'a';
                    if(newWord==endWord) return path+1;     //找到endWord的情况
                    //newWord出现在字典中，并且之前没有访问过
                    if(wordSet.find(newWord) != wordSet.end() && pathMap.find(newWord)==pathMap.end()){
                        que.push(newWord);
                        pathMap[newWord]=path+1;
                    }
                }
            }
        }
        return 0;
    }
};